1. Field of the Invention
The invention relates to the art of color image processing. For example, it finds application where an image created on, or prepared for rendering on, a first or source device is prepared for rendering on a second or destination device.
2. Description of Related Art
When an image is prepared for rendering on an electronic device the image is represented as a set of pixels. Each pixel describes a small portion of the image in terms of colorant pixel values for the colorants available on the rendering device. For example, typically a cathode ray tube (CRT) based computer display screen is comprised of red (R), green (G) and blue (B) phosphors. An image prepared for display on a CRT is described with a set of pixels. Each pixel describes the intensity with which the red, green and blue phosphors are to be illuminated on a small portion of the CRT. A similar procedure is followed when an image is prepared for rendering on a printing device. Currently, at least some color printing devices apply cyan (C), magenta (M), yellow (Y), and sometimes black (K) colorants to a print medium, such as paper or velum, in order to render an image. Such printing devices are said to operate in a CMY or CMYK color space. When an image is prepared for rendering on a color-printing device, the image is represented as a set of pixels. Each pixel describes a small portion of the image by calling for an appropriate mixture of the available colorants. Typically, the pixel value for each colorant can range from 0 to 255. The higher a colorant""s pixel value is, the more of that colorant the color image processor applies to the print medium. In a system employing 8-bit precision for the colorant signals, the number 255 represents the maximum or fully saturated amount of colorant. The number 0 is used when none of a particular colorant is required.
In a CRT operating in RGB (red, green blue) space, fully saturated red is described by a pixel calling for R=255, G=0, B=0. In a printer operating in CMYK (cyan, magenta, yellow, black) space, fully saturated red is described by a pixel calling for C=0, M=255, Y=255, K=0. Magenta and yellow colorants combine through simple subtractive mixing and are perceived as red. There is no guarantee that the red described in RGB space and displayed on the CRT is the same red described in CMYK space and printed on a page. In fact, it is quite likely that the spectral properties of the red phosphor used in the CRT will be different than the spectral properties of the subtractively mixed magenta and yellow colorants of a particular printer.
As mentioned above, the CRT and the CMYK printer use different materials to generate the perception of color. The materials used impact a set of colors that each device can reproduce.
The set of colors a device can produce is referred to as the color gamut of the device. There is no guarantee that a color that can be produced by a first device is within the color gamut of a second device. This is even true when both devices are CMYK printers.
Where color matching is required between two devices such as the CRT operating in RGB space and the printer operating in CMYK space, transforms based on calibration and measurement are required. In such a situation it is possible, for example, that the pure red RGB CRT pixel mentioned above, is mapped to a CMYK printer pixel calling for a less than fully saturated magenta component and a small amount of a cyan component. For example, the CMYK version of the original RGB red pixel referred to above might call for C=27, M=247, Y=255, K=0. Furthermore, if one wants to print a copy of the original pure red RGB CRT pixel on a second printer it is quite likely that a second transform will have to be used. That transform may translate the original RGB CRT pixel to a second CMYK pixel. For example, the second transform may map the original RGB CRT pixel to a second CMYK pixel calling for C=20, M=234, Y=240, K=35. One reason two different CMYK printers may require different transforms is that different printers use different colorants. For example, a first magenta colorant used in a first printer may have a different spectral content than a second magenta colorant used in a second printer. Likewise, a first yellow colorant used in a first printer may have a different spectral content than a second yellow colorant used in a second printer.
From the foregoing discussion it can be seen that an image prepared for rendering on a first device may need to be transformed if it is to be properly rendered on a second device. Such a transformation is an attempt to emulate the first or source device onto the second or destination device. In order to achieve calorimetric content matching, the emulation of the color gamut of the CRT on the first CMYK printer caused the red CRT pixel to be mapped to a first CMYK pixel calling for C=27, M=247, Y=255, K=0. The emulation of the color gamut of the CRT on the second CMYK printer caused the red CRT pixel to be mapped to the second CMYK pixel calling for C=20, M=234, Y=240, K=35. Obviously, therefore, even where there is no RGB CRT image involved, an image prepared for printing on the first printer may have to be transformed before its spectral content can be matched on the second printer. In such a situation the first printer is said to be emulated on the second printer.
For example, when, a photographic image has been prepared for rendering on a first CMYK device, for example a Standard Web Offset Printing (SWOP) device, but must then be rendered on a second CMYK device, for example, a xerographic printer, a xe2x80x9c4 to 4xe2x80x9d transform is typically used to emulate the first device on the second device.
An image processor must be able to satisfactorily transform images, prepared for rendering on a staggeringly large number of source devices, for rendering on an equally large number of rendering devices. For example, a personal computer, configured to operate as an image processor, through the use of, for example, a web browser, word processor, or desktop publishing software, must be able to accept images created or downloaded from almost anywhere, and render the images pleasingly on any image output terminal the user connects to the personal computer. For example, the image processor must be able to pleasingly display images on a computer screen and send commands to have images rendered pleasingly on any printer the user connects to the personal computer. Similarly, document processors and copiers must transform images pleasingly and accurately. Indeed in document processors and copiers, color accuracy requirements can be very stringent. For example, in a large print job, comprising a corporate sales presentation, it is very important that colors in a company logo be reproduced accurately and consistently. Similarly, colors in a clothing catalog must match the colors on depicted garments.
Typically transformations are carried out through the use of look up tables. For example, an image prepared for rendering in a RGB color space of a computer monitor, is transformed into a CMYK color space of a printer, through the use of a three-dimensional look up table. Each of the RGB parameters is used as an axis or index into the look up table. The RGB parameters are typically represented by 8-bit values for each of the R, G, and B components. Such a 24-bit RGB vector is capable of addressing over 16.77 million locations or describing over 16.77 million colors. However, look up tables of this size are prohibitively expensive and physically impractical. Therefore, such looks look up tables are typically partitioned into a smaller size, such as, for example, 16xc3x9716xc3x9716 (4096) table locations or nodes. Each node stores, for example, a CMYK value. CMYK values of points not directly represented by nodes, are determined by a form of interpolation among nodes of the look up table (LUT).
An illustration of the operation of a prior art look up table is instructive. Referring to FIG. 1, an input RGB value is used to determine index values r, g, b into the table 112. The index values are used to locate the transformation data within the table. For example, the index values corresponding to a point 116 do not coincide with any node location 120. Therefore, a transformation value is not directly available from the table 112. Instead, the conversion is accomplished by interpolating between the CMYK values stored in nodes 124 corresponding to the point 116. For example, the nodes 124 correspond to the point 116 because they are the nodes 124 nearest the input point 116. The input RGB color is defined in three dimensions. Therefore, the interpolation is done in three dimensions. Common examples of 3-D interpolation techniques include trilinear, tetrahedral, and prism interpolation. Of these, tetrahedral interpolation is the fastest method, requiring interpolation only among 4 nodes. (The trilinear and prism schemes utilize 8 and 6 nodes, respectively.) All these techniques require several multiplication, addition, shift, and comparison operations for each output signal or parameter at each pixel; and are often implemented with special purpose hardware. This interpolated CMYK value is then output. Typically, the output is eventually rendered, for example, on a printer.
As depicted in FIG. 1, tiling in prior art look up tables is even and regular. That is to say, each tile is a cube, and the dimensions of each cube are the same. For example, each cube or tile is, four parameter value increments wide, four parameter value increments high, and four parameter value increments deep. Such a look up table includes 26,144 tiles or cubes arranged in a grid of 64xc3x9764xc3x9764 cubes or tiles. In other words, every fourth parameter value is represented by a node. For example, a red axis has a nodes at R=0, 12 . . . 251, 255. Likewise a green axis has nodes that G=0, 12 . . . 251, 255 and a blue axis has nodes at B=0, 12 . . . 251, 255. Those skilled in the art will recognize that determining which cube, tile, or nodes to use, in a prior art look up table, to determine a transformation value for a set of RGB parameter values is a trivial matter. For example, where the pixel parameter values are represented by eight bit words, an appropriate tile, is found by shifting the bits in the eight bit words. For example, R greater than  greater than 2, G greater than  greater than 2, B greater than  greater than 2 shifts bits representing an RGB parameter value, two positions to the right, leaving the six highest order bits in each parameter for use as an index or address an appropriate node. The two low order bits of the three values indicate the position corresponding to the input color description within the cube or tile. The low order bits are used in interpolating between the nodes of the cube or tile.
This indexing and tile accessing method is very fast. However, the speed comes at a price. In order to use this prior art indexing method, one is forced to quantize or tile a color space into equal, regularly sized and regularly shaped tiles. Furthermore, one is forced to use a fine quantization (small tile size) that ensures the required transformation accuracy is achieved throughout the look up table, even though some parts of the look up table may require only coarse quantization. This means that these prior art look up tables consume more memory than would otherwise be required.
In order to reduce memory consumption while maintaining or even improving image transformation accuracy, a method and apparatus operative for transforming a description of a color from a first color space, defined by first color space parameters, into a second color space, defined by second color space parameters, has been developed. The method comprises the steps of examining a relationship between the first color space and the second color space, dividing the first color space into a plurality of tiles, each tile being of selected size and shape, the size and shape of each tile being based on the relationship between the first color space and the second color space, the tiles being defined by nodes, the nodes relating parameter values in the first color space to parameters values in the second colors space, and enumerating each tile.
Furthermore, one embodiment of the method is operative for transforming a description of a color from a first color space defined by first color space parameters to a second color space defined by second color space parameters. The embodiment of the method comprises the steps of examining a relationship between the first color space and the second color space, creating a set of transformation rules, each rule in the set operative over a particular region of the first color space, associating each rule with a bit position in a rule association vector template, associating each first color space parameter value with a particular rule association vector, setting bits in a particular rule association vector to associate a particular first color space parameter value with transformation rules that are operative over regions of the first color space that are associated with the particular first color space parameter value, selecting an image pixel describing a color in terms of a particular set of first color space parameter values for transformation into an image pixel describing a color in terms of a particular set of second color space parameter values, determining an intersection of rule association vectors of the particular set of first color space parameter values, and transforming the first color space parameter values into a set of second color space parameter values by following a transformation rule indicated by the intersection of rule association vectors.
Another aspect of the present invention is an image processor operative to transform a first image description, based in a first color space, described by a set of first color space parameters, into a second image description, based in a second color space, described by a set of second color space parameters. The image processor includes a set of transformation rules, and a set of rule association vectors. Each rule association vector is related to a particular first color space parameter value. Additionally, each rule association vector identifies particular transformation rules associated with the particular first color space parameter value. The image processor further comprises a transformation rule selector operative to use the rule association vectors to find an intersection of rules associated with a given set of first color space parameter values and to thereby select a rule for execution based on the intersection.
One advantage of the present invention resides in a reduction in memory required to store color transformation look up tables.
Another advantage of the present invention is found in design flexibility afforded by the freedom to use rule indexing transformation processes rather than being restricted to transformation by interpolation between look up table nodes.
Yet another advantage of the present invention is apparent in improved image transformations provided by an elimination of design compromise. Since fine look up table tiling or quantization can be used where needed and any extra memory used by the fine tiling can be compensated by using coarse tiling where coarse can be tolerated, fewer trade offs have to be made with regard to look up table quantization and required memory.
Yet another advantage of the present invention is that the method is performed in a deterministic number of steps. Appropriate transformation tiles are found in the same number of steps no matter what color is represented by an input color description or pixel.
Still other advantages of the present invention will become apparent to those skilled in the art upon a reading and understanding of the detail description below.